/* map.c - simple, highly-limited container class.
 *
 * We assume nothing is ever deleted, and caller supplies (and retains)
 * storage for all keys and objects to be placed in a map.
 */
#include "map.h"
#include <string.h>
#include <stdio.h>
#include <assert.h>

#define LOADFACTOR  (8)
#define CHUNKSIZE   (128)

static
size_t      Primes[] =
    {
        13, 59, 97, 257, 499, 977, 2083, 4019, 8011, 9973
    };

#define NPRIMES (sizeof(Primes)/sizeof(Primes[0]))


typedef struct  TMapLink
    {
    struct TMapLink*    Next;
    void*       Key;
    size_t      KeyLen;
    void*       Value;
    }           TMapLink;

typedef struct  TMap
    {
    size_t      HashTableSize;
    TMapLink**  HashTable;
    TMapCompare Compare;
    int         NLinks;
    }           TMap;

/* NewLink() - allocate a new TMapLink structure.
 *
 * Some insane impulse towards optimization leads me to make a
 * chunk allocator, even though I waste memory and CPU with abandon
 * elsewhere.
 */
TMapLink*   NewLink(void)
    {
    TMapLink*           Result;
    static TMapLink*    FreeList = NULL;

    if(FreeList == NULL)
        {
        int     iLink;

        FreeList    = (TMapLink*)calloc(CHUNKSIZE, sizeof(TMapLink));
        assert(FreeList != NULL);
        for(iLink = 0; iLink < (CHUNKSIZE-1); ++iLink)
            FreeList[iLink].Next    = &FreeList[iLink+1];
        /* calloc() already ensured final link.Next is zero (NULL) */
        }
    Result      = FreeList;
    FreeList    = FreeList->Next;

    return Result;
    }

int     DefCmp(void* A, size_t ALen, void* B, size_t BLen)
    {
    int     Result  = 0;

    if(ALen == BLen)
        Result  = memcmp(A, B, ALen);

    return Result;
    }

MAP     MapCreate(TMapCompare Compare)
    {
    TMap*       Result;

    Result  = (TMap*)calloc(1, sizeof(TMap));
    assert(Result != NULL);

    if(Compare == NULL)
        Compare = DefCmp;
    Result->Compare         = Compare;

    Result->HashTableSize   = Primes[0];
    Result->HashTable       = (TMapLink**)calloc(Result->HashTableSize, sizeof(TMapLink*));
    assert(Result->HashTable != NULL);

    return (MAP)Result;
    }

size_t  FindBucket(TMap* Map, void* Key, size_t KeyLen)
    {
    size_t  Hash    = 0;
    char*   Rover;

    if(KeyLen == 0) /* if key is really an int */
        {
        Rover   = (char*)&Key;
        KeyLen  = sizeof(void*);
        }
    else
        Rover   = (char*)Key;
    while(KeyLen--)
        Hash    = (Hash << 5) ^ *Rover++;

    return Hash % Map->HashTableSize;
    }

void*   MapFind(MAP Handle, void* Key, size_t KeyLen)
    {
    size_t      Bucket;
    TMap*       Map;
    TMapLink*   Rover;
    void*       Result  = NULL;

    Map     = (TMap*)Handle;
    assert(Map != NULL);
    Bucket  = FindBucket(Map, Key, KeyLen);
    Rover   = Map->HashTable[Bucket];
    while(Rover != NULL)
        if(!Map->Compare(Rover->Key, Rover->KeyLen, Key, KeyLen))
            {
            Result  = Rover->Value;
            break;
            }
        else
            Rover   = Rover->Next;
    return Result;
    }

void*   MapAdd(MAP Handle, void* Key, size_t KeyLen, void* Value)
    {
    size_t      Bucket;
    TMap*       Map;
    TMapLink*   Rover;
    void*       Result  = NULL;
    TMapLink*   Target;

    Map     = (TMap*)Handle;
    assert(Map != NULL);
    assert(Map->HashTableSize > 0);
    Bucket  = FindBucket(Map, Key, KeyLen);
    Rover   = Map->HashTable[Bucket];
    while(Rover != NULL)
        if(!Map->Compare(Rover->Key, Rover->KeyLen, Key, KeyLen))
            {
            Result  = Rover->Value;
            break;
            }
        else
            Rover   = Rover->Next;
    /* if this key already in use */
    if(Result)  
        Target  = Rover;
    else
        {
        Result  = Value;
        Target  = NewLink();
        Target->Next    = Map->HashTable[Bucket];
        Map->HashTable[Bucket]  = Target;
        ++Map->NLinks;
        }
    if((Map->NLinks / Map->HashTableSize) > LOADFACTOR)
        {
        /* ??? enlarge hash table */
        }
    Target->Key     = Key;
    Target->KeyLen  = KeyLen;
    Target->Value   = Value;

    return Result;
    }

